package cj_code


import std.collection.*
import std.core.*


// =======================
// 一、基础数据结构：状态 和 NFA
// =======================

// 状态
class State {
    public var name: String                  // 状态名称
    public var isAccept: Bool                // 是否为接受态
    public var transitions: HashMap<String, ArrayList<State>> // 转移表

    init() {
        this.name = ""
        this.isAccept = false
        this.transitions = HashMap<String, ArrayList<State>>()
    }

    init(name: String, isAccept: Bool) {
        this.name = name
        this.isAccept = isAccept
        this.transitions = HashMap<String, ArrayList<State>>()
    }

    // 添加一条转移
    func addTransition(symbol: String, state: State) {
        if (!this.transitions.contains(symbol)) {
            this.transitions[symbol] = ArrayList<State>()
        }
        let arr = this.transitions[symbol]
        arr.add(state)
        this.transitions[symbol] = arr
    }

    func toString(): String {
        "状态名称: ${this.name}, 是否为接受态: ${this.isAccept}"
    }
}

// NFA
class NFA {
    public var startState: State         // 起始状态
    public var acceptState: State        // 接受态
    public var states: ArrayList<State>  // 状态列表
    public var statesNum: Int64          // 状态数量

    // 单字符的 NFA 构造函数
    init(inputChar: String) {
        this.startState = State("0", false)
        this.acceptState = State("1", true)
        this.states = ArrayList<State>()
        this.states.add(this.startState)
        this.states.add(this.acceptState)
        this.statesNum = 2

        // 起始状态经 inputChar 转移到接受状态
        this.startState.addTransition(inputChar, this.acceptState)
    }

    // 向 NFA 中添加状态
    func addState(s: State) {
        this.states.add(s)
        this.statesNum = this.states.size
    }

    // 刷新状态数量
    func modifyNum() {
        this.statesNum = this.states.size
    }

    // 打印 NFA 的结构
    func toString(): String {
        var out = "NFA，包含 ${this.statesNum} 个状态：\n"
        // 先明确给出起始状态和接受状态
        out = "${out}起始状态: ${this.startState.name}，接受状态: ${this.acceptState.name}\n"

        for (state in this.states) {
            out = "${out}状态 名称: ${state.name}, 是否接受态: ${state.isAccept}\n"
            for (k in state.transitions.keys()) {
                let arr = state.transitions[k]
                if (arr.size > 0) {
                    out = "${out}${state.name} --${k}--> "
                    for (ns in arr) {
                        out = "${out}${ns.name} "
                    }
                    out = "${out}\n"
                }
            }
        }
        out
    }
}

// =======================
// NFA的DOT可视化输出
// =======================
func nfaToDot(nfa: NFA): String {
    var out = "digraph NFA {\n"
    out = "${out}  rankdir=LR;\n"
    out = "${out}  node [shape=circle];\n"
    // 虚拟起始结点,指向真正的起始状态
    out = "${out}  __start__ [shape=point];\n"
    out = "${out}  __start__ -> ${nfa.startState.name};\n"

    // 所有结点:接受态双圈
    for (state in nfa.states) {
        if (state.isAccept) {
            out = "${out}  ${state.name} [shape=doublecircle];\n"
        } else {
            out = "${out}  ${state.name} [shape=circle];\n"
        }
    }

    // 所有边
    for (state in nfa.states) {
        for (k in state.transitions.keys()) {
            let arr = state.transitions[k]
            let label = if (k == " ") { "ε" } else { k }
            for (ns in arr) {
                out = "${out}  ${state.name} -> ${ns.name} [label=\"${label}\"];\n"
            }
        }
    }

    out = "${out}}\n"
    out
}

// =======================
// 二、正则表达式处理：中缀 → 后缀
// =======================

// 判断是否为字母（本实验只支持字母作为输入符号）
func isLetter(r: Rune): Bool {
    (r >= r'a' && r <= r'z') || (r >= r'A' && r <= r'Z')
}

// 将隐式连接插入显式连接符 '.'
// 例如 ab 变成 a.b，a(b) 变成 a.(b)，a*b 变成 a*.b
func regexInsertConcatenation(regex: String): String {
    var result = ""
    var prevSet: Bool = false
    var prevRune: Rune = r' '
    for (ch in regex.runes()) {
        if (prevSet) {
            let cIsToken = isLetter(prevRune) || prevRune == r')' || prevRune == r'*'
            let nIsToken = isLetter(ch) || ch == r'('
            if (cIsToken && nIsToken) {
                result = "${result}."
            }
        }
        result = "${result}${ch.toString()}"
        prevRune = ch
        prevSet = true
    }
    result
}

// 运算符优先级
func precedence(op: Rune): Int64 {
    match (op) {
        case r'*' => 3
        case r'.' => 2
        case r'|' => 1
        case _    => 0
    }
}

// 中缀正则转后缀（支持 | . * 和括号）
func regexToPostfix(regex: String): String {
    let r = regexInsertConcatenation(regex)
    var output = ""
    var ops = ArrayList<Rune>()    // 运算符栈
    var opsLen: Int64 = 0
    let arr = r.toRuneArray()
    var i: Int64 = 0

    while (i < arr.size) {
        let ch = arr[i]
        if (isLetter(ch)) {
            // 操作数直接输出
            output = "${output}${ch.toString()}"
        } else if (ch == r'(') {
            if (opsLen < ops.size) { ops[opsLen] = ch } else { ops.add(ch) }
            opsLen += 1
        } else if (ch == r')') {
            while (opsLen > 0 && ops[opsLen - 1] != r'(') {
                let top = ops[opsLen - 1]
                opsLen -= 1
                output = "${output}${top.toString()}"
            }
            if (opsLen > 0 && ops[opsLen - 1] == r'(') {
                opsLen -= 1
            }
        } else {
            // 其他运算符，根据优先级弹栈
            while (opsLen > 0 && precedence(ops[opsLen - 1]) >= precedence(ch)) {
                let top = ops[opsLen - 1]
                opsLen -= 1
                output = "${output}${top.toString()}"
            }
            if (opsLen < ops.size) { ops[opsLen] = ch } else { ops.add(ch) }
            opsLen += 1
        }
        i += 1
    }

    // 栈中剩余运算符全部弹出
    while (opsLen > 0) {
        let top = ops[opsLen - 1]
        opsLen -= 1
        output = "${output}${top.toString()}"
    }
    output
}


// =======================
// 三、Thompson 构造：后缀 → NFA
// =======================

// 连接：nfa1 · nfa2
func nfaConcatenate(nfa1: NFA, nfa2: NFA): NFA {
    // 原 nfa1 的接受态不再是接受态
    nfa1.acceptState.isAccept = false
    // 在接受态加一条 epsilon 转移到 nfa2 的起始态
    nfa1.acceptState.addTransition(" ", nfa2.startState)

    // 合并状态集合
    for (s in nfa2.states) {
        nfa1.addState(s)
    }

    // nfa1 的接受态更新为 nfa2 的接受态
    nfa1.acceptState = nfa2.acceptState
    nfa1.modifyNum()
    nfa1
}

// 闭包：nfa*
func nfaClosure(nfa: NFA): NFA {
    let newStart = State("", false)
    let newAccept = State("", true)

    // newStart 通过 epsilon 指向原 start 和 newAccept（0 次）
    newStart.addTransition(" ", nfa.startState)
    newStart.addTransition(" ", newAccept)

    // 原接受态不再为接受态
    nfa.acceptState.isAccept = false
    // 原接受态 -> epsilon -> 原 start（回环）
    nfa.acceptState.addTransition(" ", nfa.startState)
    // 原接受态 -> epsilon -> newAccept（退出）
    nfa.acceptState.addTransition(" ", newAccept)

    // 把 newStart/newAccept 加入状态集合
    nfa.addState(newStart)
    nfa.addState(newAccept)

    // 给两个新状态命名为末尾两个索引
    let idxStart = nfa.states.size - 2
    let idxAccept = nfa.states.size - 1
    if (idxStart >= 0) { newStart.name = idxStart.toString() }
    if (idxAccept >= 0) { newAccept.name = idxAccept.toString() }

    nfa.startState = newStart
    nfa.acceptState = newAccept
    nfa.modifyNum()
    nfa
}

// 并：nfa1 | nfa2
func nfaOr(nfa1: NFA, nfa2: NFA): NFA {
    let newStart = State("", false)
    let newAccept = State("", true)

    // 新起点 epsilon 指向两个子 NFA 的起点
    newStart.addTransition(" ", nfa1.startState)
    newStart.addTransition(" ", nfa2.startState)

    // 原接受态不再接受
    nfa1.acceptState.isAccept = false
    nfa2.acceptState.isAccept = false

    // 两个原接受态都 epsilon 指向 newAccept
    nfa1.acceptState.addTransition(" ", newAccept)
    nfa2.acceptState.addTransition(" ", newAccept)

    // 合并状态
    for (s in nfa2.states) {
        nfa1.addState(s)
    }
    nfa1.addState(newStart)
    nfa1.addState(newAccept)

    // 为新状态命名
    let idxStart = nfa1.states.size - 2
    let idxAccept = nfa1.states.size - 1
    if (idxStart >= 0) { newStart.name = idxStart.toString() }
    if (idxAccept >= 0) { newAccept.name = idxAccept.toString() }

    nfa1.startState = newStart
    nfa1.acceptState = newAccept
    nfa1.modifyNum()
    nfa1
}

// 后缀表达式转 NFA
func postfixToNFA(postfix: String): NFA {
    let stack = ArrayList<NFA>()
    var stackLen: Int64 = 0

    for (ch in postfix.runes()) {
        if (isLetter(ch)) {
            let s = ch.toString()
            if (stackLen < stack.size) { stack[stackLen] = NFA(s) } else { stack.add(NFA(s)) }
            stackLen += 1
        } else if (ch == r'*') {
            let a = stack[stackLen - 1]
            stackLen -= 1
            let res = nfaClosure(a)
            if (stackLen < stack.size) { stack[stackLen] = res } else { stack.add(res) }
            stackLen += 1
        } else if (ch == r'.') {
            let a = stack[stackLen - 1]
            stackLen -= 1
            let b = stack[stackLen - 1]
            stackLen -= 1
            let res = nfaConcatenate(b, a)
            if (stackLen < stack.size) { stack[stackLen] = res } else { stack.add(res) }
            stackLen += 1
        } else if (ch == r'|') {
            let a = stack[stackLen - 1]
            stackLen -= 1
            let b = stack[stackLen - 1]
            stackLen -= 1
            let res = nfaOr(b, a)
            if (stackLen < stack.size) { stack[stackLen] = res } else { stack.add(res) }
            stackLen += 1
        }
    }

    let resultNFA = stack[0]
    renumberNFA(resultNFA)
    resultNFA
}

// 给 NFA 状态重新编号（0,1,2,...）
func renumberNFA(nfa: NFA) {
    var idx: Int64 = 0
    for (s in nfa.states) {
        s.name = idx.toString()
        idx += 1
    }
    nfa.modifyNum()
}


// =======================
// 四、NFA 上的 epsilon-closure / move / testNFA
// =======================

// 判断一个状态是否在状态集合中
func containsState(arr: ArrayList<State>, s: State): Bool {
    for (x in arr) {
        if (x.name == s.name) {
            return true
        }
    }
    false
}

// epsilon 闭包
func epsilonClosure(states: ArrayList<State>): ArrayList<State> {
    let result = ArrayList<State>()
    let queue = ArrayList<State>()
    var qLen: Int64 = 0

    // 初始化
    for (s in states) {
        if (!containsState(result, s)) {
            result.add(s)
        }
        if (qLen < queue.size) {
            queue[qLen] = s
        } else {
            queue.add(s)
        }
        qLen += 1
    }

    // BFS 展开所有 epsilon 转移
    while (qLen > 0) {
        let cur = queue[qLen - 1]
        qLen -= 1
        if (cur.transitions.contains(" ")) {
            let arr = cur.transitions[" "]
            for (ns in arr) {
                if (!containsState(result, ns)) {
                    result.add(ns)
                    if (qLen < queue.size) {
                        queue[qLen] = ns
                    } else {
                        queue.add(ns)
                    }
                    qLen += 1
                }
            }
        }
    }
    result
}

// move 操作：从一组状态读一个符号能到达的状态集合
func move(states: ArrayList<State>, ch: String): ArrayList<State> {
    let result = ArrayList<State>()
    for (s in states) {
        if (s.transitions.contains(ch)) {
            let arr = s.transitions[ch]
            for (ns in arr) {
                if (!containsState(result, ns)) {
                    result.add(ns)
                }
            }
        }
    }
    result
}

// 利用 epsilonClosure 和 move 在 NFA 上测试一个字符串是否被接受
func testNFA(nfa: NFA, input: String): Bool {
    // 初始状态集合为 startState 的 epsilon 闭包
    let startSet = ArrayList<State>()
    startSet.add(nfa.startState)
    var current = epsilonClosure(startSet)

    // 逐字符读取
    for (ch in input.runes()) {
        let sym = ch.toString()
        let moved = move(current, sym)
        current = epsilonClosure(moved)
        if (current.size == 0) {
            break
        }
    }

    // 只要当前集合中存在接受态，则接受
    for (s in current) {
        if (s.isAccept) {
            return true
        }
    }
    false
}


// =======================
// 五、DFA 结构 + NFA → DFA + DFA 测试
// =======================

// 判断两个状态集合是否相同
func sameSet(a: ArrayList<State>, b: ArrayList<State>): Bool {
    if (a.size != b.size) {
        return false
    }
    for (s in a) {
        if (!containsState(b, s)) {
            return false
        }
    }
    true
}

// DFA 状态
class DFAState {
    public var name: String
    public var states: ArrayList<State>   // 对应的 NFA 状态子集
    public var isAccept: Bool
    public var transitions: HashMap<String, DFAState>

    init() {
        this.name = ""
        this.states = ArrayList<State>()
        this.isAccept = false
        this.transitions = HashMap<String, DFAState>()
    }

    init(name: String, isAccept: Bool) {
        this.name = name
        this.states = ArrayList<State>()
        this.isAccept = isAccept
        this.transitions = HashMap<String, DFAState>()
    }

    func addTransition(sym: String, target: DFAState) {
        this.transitions[sym] = target
    }

    func toString(): String {
        var out = "DFA状态 ${this.name}，包含NFA状态："
        for (s in this.states) {
            out = "${out}${s.name} "
        }
        out = "${out}，是否接受态: ${this.isAccept}"
        out
    }
}

// DFA
class DFA {
    public var startState: DFAState
    public var states: ArrayList<DFAState>
    public var acceptStates: ArrayList<DFAState>

    init(startState: DFAState) {
        this.startState = startState
        this.states = ArrayList<DFAState>()
        this.acceptStates = ArrayList<DFAState>()
    }

    func addState(s: DFAState) {
        this.states.add(s)
    }

    func addAcceptState(s: DFAState) {
        this.acceptStates.add(s)
    }

    func toString(): String {
        var out = "DFA，共 ${this.states.size} 个状态：\n"

        // 明确打印起始状态
        out = "${out}起始状态: ${this.startState.name}\n"

        // 明确打印接受状态集合
        var acc = ""
        for (s in this.acceptStates) {
            acc = "${acc}${s.name} "
        }
        if (this.acceptStates.size > 0) {
            out = "${out}接受状态集合: { ${acc}}\n"
        } else {
            out = "${out}接受状态集合: { }\n"
        }

        // 然后再打印每个状态的详细信息与转移
        for (st in this.states) {
            out = "${out}${st.toString()}\n"
            for (k in st.transitions.keys()) {
                let t = st.transitions[k]
                out = "${out}  ${st.name} --${k}--> ${t.name}\n"
            }
        }
        out
    }
}
// =======================
// DFA的DOT可视化输出
// =======================
func dfaToDot(dfa: DFA): String {
    var out = "digraph DFA {\n"
    out = "${out}  rankdir=LR;\n"
    out = "${out}  node [shape=circle];\n"
    // 虚拟起始结点
    out = "${out}  __start__ [shape=point];\n"
    out = "${out}  __start__ -> ${dfa.startState.name};\n"

    // 结点:接受态双圈
    for (st in dfa.states) {
        if (st.isAccept) {
            out = "${out}  ${st.name} [shape=doublecircle];\n"
        } else {
            out = "${out}  ${st.name} [shape=circle];\n"
        }
    }

    // 边
    for (st in dfa.states) {
        for (k in st.transitions.keys()) {
            let t = st.transitions[k]
            out = "${out}  ${st.name} -> ${t.name} [label=\"${k}\"];\n"
        }
    }

    out = "${out}}\n"
    out
}

// 从正则表达式中收集字母表
func collectAlphabetFromRegex(regex: String): ArrayList<String> {
    let result = ArrayList<String>()
    for (ch in regex.runes()) {
        if (isLetter(ch)) {
            let s = ch.toString()
            var exists = false
            for (x in result) {
                if (x == s) {
                    exists = true
                }
            }
            if (!exists) {
                result.add(s)
            }
        }
    }
    result
}

// NFA → DFA（子集构造）
func nfaToDfa(nfa: NFA, alphabet: ArrayList<String>): DFA {
    // 起始子集：start 的 epsilon 闭包
    let startSet = ArrayList<State>()
    startSet.add(nfa.startState)
    let startClosure = epsilonClosure(startSet)

    let startDfa = DFAState("0", false)
    for (s in startClosure) {
        startDfa.states.add(s)
        if (s.isAccept) {
            startDfa.isAccept = true
        }
    }

    let dfa = DFA(startDfa)
    dfa.addState(startDfa)
    if (startDfa.isAccept) {
        dfa.addAcceptState(startDfa)
    }

    let worklist = ArrayList<DFAState>()
    var wLen: Int64 = 0
    worklist.add(startDfa)
    wLen = 1

    while (wLen > 0) {
        let cur = worklist[wLen - 1]
        wLen -= 1

        for (sym in alphabet) {
            let moved = move(cur.states, sym)
            if (moved.size == 0) {
                continue
            }
            let cl = epsilonClosure(moved)
            if (cl.size == 0) {
                continue
            }

            // 查找是否已有等价子集
            var existingIndex: Int64 = -1
            var idx: Int64 = 0
            while (idx < dfa.states.size) {
                let st = dfa.states[idx]
                if (sameSet(st.states, cl)) {
                    existingIndex = idx
                    break
                }
                idx += 1
            }

            if (existingIndex == -1) {
                let newName = dfa.states.size.toString()
                let newState = DFAState(newName, false)
                for (s in cl) {
                    newState.states.add(s)
                    if (s.isAccept) {
                        newState.isAccept = true
                    }
                }
                dfa.addState(newState)
                if (newState.isAccept) {
                    dfa.addAcceptState(newState)
                }

                cur.addTransition(sym, newState)
                if (wLen < worklist.size) {
                    worklist[wLen] = newState
                } else {
                    worklist.add(newState)
                }
                wLen += 1
            } else {
                let existState = dfa.states[existingIndex]
                cur.addTransition(sym, existState)
            }
        }
    }

    dfa
}

// 在 DFA 上测试字符串
func testDFA(dfa: DFA, input: String): Bool {
    var cur = dfa.startState
    for (ch in input.runes()) {
        let sym = ch.toString()
        if (!cur.transitions.contains(sym)) {
            return false
        }
        cur = cur.transitions[sym]
    }
    cur.isAccept
}


// =======================
// 六、DFA 最小化（Hopcroft 划分）
// =======================

// 找到某个状态属于哪个分组
func getPartitionIndex(state: DFAState, partition: ArrayList<ArrayList<DFAState>>): Int64 {
    var i: Int64 = 0
    while (i < partition.size) {
        let group = partition[i]
        for (s in group) {
            if (s.name == state.name) {
                return i
            }
        }
        i += 1
    }
    -1
}

// 构造 DFA 的字母表（从转移中收集）
func collectAlphabetFromDFA(dfa: DFA): ArrayList<String> {
    let alphabet = ArrayList<String>()
    for (st in dfa.states) {
        for (k in st.transitions.keys()) {
            var exists = false
            for (a in alphabet) {
                if (a == k) {
                    exists = true
                }
            }
            if (!exists) {
                alphabet.add(k)
            }
        }
    }
    alphabet
}

// DFA 最小化
func minimizeDFA(dfa: DFA): DFA {
    let alphabet = collectAlphabetFromDFA(dfa)

    // 初始划分：接受态和非接受态
    let partition = ArrayList<ArrayList<DFAState>>()
    let acceptGroup = ArrayList<DFAState>()
    let nonAcceptGroup = ArrayList<DFAState>()
    for (st in dfa.states) {
        if (st.isAccept) {
            acceptGroup.add(st)
        } else {
            nonAcceptGroup.add(st)
        }
    }
    if (acceptGroup.size > 0) {
        partition.add(acceptGroup)
    }
    if (nonAcceptGroup.size > 0) {
        partition.add(nonAcceptGroup)
    }

    var changed = true
    while (changed) {
        changed = false
        let newPartition = ArrayList<ArrayList<DFAState>>()

        for (group in partition) {
            if (group.size <= 1) {
                newPartition.add(group)
                continue
            }

            // 签名：对每个符号，看转到哪个分组
            let sigMap = HashMap<String, ArrayList<DFAState>>()

            for (st in group) {
                let sigParts = ArrayList<String>()
                for (sym in alphabet) {
                    var tgtIndex: Int64 = -1
                    if (st.transitions.contains(sym)) {
                        let tgt = st.transitions[sym]
                        tgtIndex = getPartitionIndex(tgt, partition)
                    }
                    sigParts.add(tgtIndex.toString())
                }
                var sigStr = ""
                for (p in sigParts) {
                    sigStr = sigStr + p + ","
                }

                if (!sigMap.contains(sigStr)) {
                    sigMap[sigStr] = ArrayList<DFAState>()
                }
                let arr = sigMap[sigStr]
                arr.add(st)
            }

            for (sig in sigMap.keys()) {
                let subGroup = sigMap[sig]
                newPartition.add(subGroup)
                if (subGroup.size < group.size) {
                    changed = true
                }
            }
        }

        // 更新划分
        partition.clear()
        for (g in newPartition) {
            partition.add(g)
        }
    }

    // 根据最终划分构造新的最小 DFA
    let minimized = DFA(DFAState("0", false))
    minimized.states.clear()
    minimized.acceptStates.clear()

    let stateMap = HashMap<String, DFAState>()  // 旧groupIndex -> 新状态

    var idx: Int64 = 0
    while (idx < partition.size) {
        let group = partition[idx]
        if (group.size == 0) {
            idx += 1
            continue
        }

        let rep = group[0]
        let newSt = DFAState(idx.toString(), rep.isAccept)
        // 保留一下包含的 NFA 状态集合（便于看）
        for (s in rep.states) {
            newSt.states.add(s)
        }
        minimized.addState(newSt)
        if (newSt.isAccept) {
            minimized.addAcceptState(newSt)
        }
        stateMap[idx.toString()] = newSt
        idx += 1
    }

    // 起始状态：原起始状态所在分组
    var startIndex = getPartitionIndex(dfa.startState, partition)
    if (startIndex < 0) { startIndex = 0 }
    minimized.startState = stateMap[startIndex.toString()]

    // 构造转移
    idx = 0
    while (idx < partition.size) {
        let group = partition[idx]
        if (group.size == 0) {
            idx += 1
            continue
        }
        let rep = group[0]
        let newSt = stateMap[idx.toString()]
        for (sym in alphabet) {
            if (rep.transitions.contains(sym)) {
                let tgt = rep.transitions[sym]
                let tgtIdx = getPartitionIndex(tgt, partition)
                if (tgtIdx >= 0 && stateMap.contains(tgtIdx.toString())) {
                    let newTgt = stateMap[tgtIdx.toString()]
                    newSt.addTransition(sym, newTgt)
                }
            }
        }
        idx += 1
    }

    minimized
}


// =======================
// 七、主函数：1+2+3 全部串起来
// =======================

main(args: Array<String>) {
    if (args.size < 2) {
        println("用法: cj_code <正则表达式> <测试串1> [测试串2 ...]")
        println("示例: cj_code \"a(b|c)*\" \"ab\" \"accc\" \"b\"")
        return
    }

    let regex = args[0]
    if (regex.isEmpty()) {
        println("错误: 正则表达式不能为空")
        return
    }

    // 收集所有测试字符串
    let testStrings = ArrayList<String>()
    var i: Int64 = 1
    while (i < args.size) {
        testStrings.add(args[i])
        i += 1
    }

    try {
        // ========= 目标1：正则 → NFA，并用 NFA 测试 =========
        let postfix = regexToPostfix(regex)
        println("后缀表达式: " + postfix)

        let nfa = postfixToNFA(postfix)

        println("")
        println("构造得到的 NFA：")
        println(nfa.toString())
        println("")
        println("=== NFA的DOT可视化描述,可以复制到Graphviz画图 ===")
        println(nfaToDot(nfa))

        println("")
        println("=== 使用 NFA 进行匹配测试（目标1） ===")
        println("正则表达式: " + regex)
        for (s in testStrings) {
            let ok = testNFA(nfa, s)
            println("测试字符串: \"" + s + "\" -> " + if (ok) { "接受" } else { "拒绝" })
        }

        // ========= 目标2：NFA → DFA，并用 DFA 测试 =========
        let alphabet = collectAlphabetFromRegex(regex)
        let dfa = nfaToDfa(nfa, alphabet)

        println("")
        println("构造得到的 DFA：")
        println(dfa.toString())
        println("")
        println("=== DFA的DOT可视化描述,可以复制到Graphviz画图 ===")
        println(dfaToDot(dfa))

        println("")
        println("=== 使用 DFA 进行匹配测试（目标2） ===")
        for (s in testStrings) {
            let ok = testDFA(dfa, s)
            println("测试字符串: \"" + s + "\" -> " + if (ok) { "接受" } else { "拒绝" })
        }

        // ========= 目标3：DFA 最小化，并用最小化 DFA 测试 =========
        let minimizedDFA = minimizeDFA(dfa)

        println("")
        println("最小化后的 DFA：")
        println(minimizedDFA.toString())
        println("")
        println("=== 最小化DFA的DOT可视化描述,可以复制到Graphviz画图 ===")
        println(dfaToDot(minimizedDFA))

        println("")
        println("最小化前状态数: " + dfa.states.size.toString())
        println("最小化后状态数: " + minimizedDFA.states.size.toString())

        println("")
        println("=== 使用最小化 DFA 进行匹配测试（目标3） ===")
        for (s in testStrings) {
            let ok = testDFA(minimizedDFA, s)
            println("测试字符串: \"" + s + "\" -> " + if (ok) { "接受" } else { "拒绝" })
        }

    } catch (e: Exception) {
        println("发生异常: ${e.toString()}")
    }
}
